Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Levenshtein[1] and Conway and Sloane [2] and are known to be linear over some finite fields.
A lexicode of minimum distance d and length n over a finite field is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance d from the vectors added so far. As an example, the length-3 lexicode of minimum distance 2 would consist of the vectors marked by an "X" in the following example:
Vector | In code? |
---|---|
000 | X |
001 | |
010 | |
011 | X |
100 | |
101 | X |
110 | X |
111 |
Since lexicodes are linear, they can also be constructed by means of their basis. [3]